The present invention relates to Viterbi decoding.
Viterbi decoders find many applications. One such application is in baseband decoders for European digital audio broadcast (DAB) receivers. DAB services are transmitted using a frame structure in which individual services use one or more of six subframes of a frame. A problem arises because decoders suitable for consumer equipment cannot decode all six subframes thereby limiting the available equipment to the reception of one service at a time and preventing the use of a whole frame for one high bandwidth service.
DAB services are transmitted using a convolution code, having a 7-bit constraint length, to form four polynomial codes. The decoding process is computationally intensive, typically requiring 328 DSP (digital signal processor) instructions for a one bit decoder. This is because, in order to decode the 7-bit constraint length convolution code used for DAB, processing is required for 64 states. The processing of each state requires the following stages: adding two new branch metrics to an existing path metric; identify best of the two new branch metrics; selecting the best new branch metric as the surviving path; and tracing back the surviving path.
A full-rate DAB decoder, i.e. one for decoding all of the subframes in real time, must operate at a speed of 1.9 Mbits/s, requiring operation at 623 MIPs by the DSP.
The use of Viterbi decoding of convolution coded data is described in general in Halsall, F., xe2x80x9cData Communications, Computer Network and Open Systemsxe2x80x9d, ISBN 0-201-42293-X.
Viterbi decoding comprises processing of path metrics and processing of path history data. This data is typically stored in RAM.
It is an object of the present invention to provided an improved Viterbi decoder.
It is a further object of the present invention to provide a Viterbi decoder having an increased data throughput.
It is yet a further object of the present invention to provide a Viterbi decoder which makes efficient use of silicon possible.
According to the present invention, there is provided a Viterbi decoder including memory means for storing Viterbi decoder data, comprising path metrics and/or path history data, clocked processing means for producing new Viterbi decoder data from Viterbi decoder data read from the memory means and a signal being decoded, and addressing means for addressing the memory means, wherein the memory means comprises two-port RAM means and the addressing means is configured such that Viterbi decoder data is always read from the memory means in the same state order and the addressing of the memory means for writing Viterbi data follows the same sequence as the read addressing but lags by the maximum number of control clock cycles taken between reading Viterbi data and storing of the resultant new Viterbi data. The use of the same addresses for reading and then, a predetermined period later, writing data means that the address sequence used cycles through a series of permutations, changing with each frame, so that the data is always read in a constant state order.
The particular addressing arrangement of the present invention means that two-port RAMs can be employed, resulting in a significant reduction in the amount of memory required. When the present invention is embodied in an integrated circuit, there is also a significant reduction in the area of silicon required.
Preferably, the memory means comprised first and second two-port RAM means and the addressing means is arranged for reading two path metrics or history data for two paths concurrently from respectively the first and second RAM means. More preferably, an address signal applied to the first RAM means is concurrently applied to the second RAM means. The first and second two-port RAM means may be embodied in a single RAM structure. Since the same address signals are applied concurrently to both RAM means, one RAM means can be embodied in the cells for the most significant bits and the other RAM means can be embodied in the cells for the least significant bits. For example, if each RAM means must store an 11-bit word, a single RAM that stores 22-bit words can be used. In this case, the first RAM means may comprise the cells for the 11 most significant bits and the second RAM means may comprise the cells for the 11 least significant bits.
In a preferred embodiment, the memory means comprises four two-port RAM means, two of which store path metric data and two of which store path history data. The four two-port RAM means may be embodied in a single two-port RAM structure.
According to the present invention, there is also provided a method of Viterbi decoding comprising the steps of: (a) obtaining two path metrics, the path metrics being associated with states that can be followed by the same set of states; (b) modifying said path metrics with branch metrics to produce a first pair of new path metrics for a first member of said set and a second pair of path metrics for a second member of said set, the members of each pair being derived respectively from said two path metrics; and (c) selecting the lower cost path metric of each pair.
Preferably, step (a) is performed while step (b) is being performed in respect of two path metrics obtained by an earlier performance of step (a). In other words, the processing of path metrics is pipelined.
Preferably, step (b) comprises adding a branch metric to each of said two path metrics and subtracting the same branch metric from each of said two path metrics. This may be applied cases where there is a degree of symmetry inherent in the convolution code being decoded.
Preferably, the selected path metrics are stored in a memory means from which at least one of said two path metrics was read. More preferably, selected path metrics are written to respective RAM means in dependence on the most significant bits of the binary representations of the states to which the selected path metrics relate.
Preferably, the reading of path metrics is arranged such that a first performance of step (a) and a second immediately following performance of step (a) leads to a pair of selected path metrics to be stored in one of said RAM means and a pair of selected path metrics to be stored in the other of said RAM means, and each member of one of the pairs of selected path metrics is stored concurrently with a member of the other pair of selected path metrics.
According to the present invention, there is also provided Viterbi decoder comprising first processing means for concurrently modifying two path metrics using at least one branch metric to produce a pair of new path metrics for each of two branched to states, and second processing means for concurrently processing pairs of new path metrics, produced by the first processing means, to select from each pair a path metric for a surviving path.
Preferably, there is provided memory means for storing path metrics and addressing means for reading two path metrics from the memory means, the path metrics being associated with states that can be followed by the same set of states, wherein the first processing means is arranged to process path metrics read from the memory means by means of the addressing means.
Preferably, the first processing means comprises an first adder for adding a branch metric to a first path metric read from the memory means, a second adder for adding a branch metric to a second path metric read from the memory means, a first subtracter for subtracting a branch metric from said first path metric and a second subtracter for subtracting a branch metric from said second path metric.
More preferably, the same branch metric is applied to the first and second adders and the first and second subtracters.
Preferably, the second processing means is arranged to output said selected path metrics to the memory means.
Preferably, the memory means comprises first and second RAM means and the second processing means is arranged such that said selected path metrics are output to one or other of the RAM means in dependence on values of the most significant bits of the binary representations of their associated states. More preferably, the first and second RAM means comprise two-port RAM means and the addressing means is arranged for reading said two path metrics from respectively the first and second RAM means. Conveniently, an address signal applied to the first RAM means is concurrently applied to the second RAM. The use of two-port RAM means with the preferred addressing arrangement reduces the amount of RAM that must be provided vis-à-vis the prior art.
Preferably, the addressing means is configured such that path metrics are always read from the memory means in the same order and the addressing of the memory means for writing surviving path metrics follows the same sequence as the read addressing but lags by the maximum number of control clock cycles taken between reading two path metrics and storing of the resultant surviving path metrics.
According to the present invention, there is further provided a method of Viterbi decoding comprising the steps of: (a) concurrently obtaining history data for paths to two states in a Viterbi trellis; (b) concurrently determining which path segments to two succeeding states survive; and (c) concurrently adding indications of the new surviving path segments to the history data to produce modified history data.
Preferably, step (c) includes removing the oldest element of each history data.
Preferably, the history data is obtained from memory means and the modified history data is written to memory means. More preferably, the history data is always read in the same state order and the addressing of the memory means for writing modified history data follows the same sequence as the read addressing for history data but lags by the maximum number of control clock cycles taken between reading the history data and storing of the resultant modified history data.
According to the present invention, there is further provided a Viterbi decoder comprising first means for concurrently obtaining history data for paths to two states in a Viterbi trellis, second means for concurrently determining which path segments to two succeeding states survive, and third means for concurrently adding indications of the new surviving path segments to the history data to produce modified history data.
Preferably, the third means is configured to remove the oldest element of each history data.
Preferably, there is provided memory means from which the history data is obtained by the first means and memory means to which the modified history data is written by the third means. More preferably, there is provided addressing means for addressing the memory means such that the history data is always read in the same state order and the addressing of the memory means for writing modified history data follows the same sequence as the read addressing for history data but lags by the maximum number of control clock cycles taken between reading the history data and storing of the resultant modified history data.
According to the present invention, there is further provided a method of Viterbi decoding comprising the steps of: (a) identifying a state having the lowest cost path; (b) extracting a bit of a binary sequence representing said path, the bit being sufficiently old for convergence of paths to be reasonably expected; and (c) outputting the extracted bit as a decoded data bit.
In the conventional approach, it is assumed that the paths will converge when traced back a certain number of frames. However, it has been discovered that this assumption cannot be relied upon in practice and that the present invention leads to a reduced error rate.
Preferably, the extracted bit is the oldest bit of said binary sequence.
Preferably, step (a) is performed concurrently with the processing of path metrics.
Preferably, the method includes obtaining two path metrics, the path metrics being associated with states that can be followed by the same set of states; modifying said path metrics with branch metrics to produce a first pair of new path metrics for a first member of said set and a second pair of path metrics for a second member of said set, the members of each pair being derived respectively from said two path metrics; selecting, as surviving path metrics, the lower cost path metric of each pair; selecting the lower cost path metric of a pair of surviving path metrics, storing the lower cost path metric of the selected path metric and the lowest cost previously selected and stored path metric; and, when the path metrics for all states have been processed, extracting and outputting the oldest bit of the binary sequence for the stored path metric.
According to the present invention, there is further provided a Viterbi decoder comprising first means for identifying a state having the lowest cost path, second means for extracting a bit of a binary sequence representing said path, the bit being sufficiently old for convergence of paths to be reasonably expected, and third means for outputting the extracted bit as a decoded data bit.
Preferably, the extracted bit is the oldest bit of said binary sequence.
Preferably, there is provided first processing means for concurrently modifying two path metrics using at least one branch metric to produce a pair of new path metrics for each of two branched to states, and second processing means for concurrently processing pairs of new path metrics, produced by the first processing means, to select from each pair a path metric for a surviving path, and the first means comprises a first comparator for identifying the lower cost path from of a pair of surviving path metrics, a first multiplexer for selecting the path metric for the identified path, a register for storing a path metric, a second comparator for determining the lower cost path from the metric of the identified path and the contents of the register, a second multiplexer for selecting the lower cost path and routing its path metric to the register.
Preferably, there is provided means responsive to the comparators for routing the extracted bit associated with the path metric, making its way to the register, to a 1-bit register and means responsive to the end of path metric processing for all states to output the contents of the 1-bit register as a decoded data bit.
The aspects of the present invention set out above may be employed individually or in any combination of two or more.
The parallel, pipelined architecture employed in aspects of the present invention results in a greatly increased data throughput with only a marginal increase in the number of gates used.